package com.autumn.algorithm;

/**
 * 相交链表
 * 给定两个链表的头节点 headA 和 headB，找出并返回两个单链表相交的起始节点，若没相交则返回null
 * 注：题目数据保证不存在环，函数返回结果后，链表保持原始结构
 */
public class Algorithm11GetIntersectionNode {
    /**
     * 解法一：双指针遍历
     * 两边遍历结束后切换到对方链表遍历，相等时即为相交初始位置，null为不相交
     * 时间复杂度 O(m+n)
     * 空间复杂度 O(1)
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            //pA为空时，指向headB开始遍历
            pA = pA == null ? headB : pA.next;
            //pB为空时，指向headA开始遍历
            pB = pB == null ? headA : pB.next;
        }
        //当两个指针相等时，即为相交的初始节点，若为null则说明不相交
        return pA;
    }

    /**
     * 解法二：双指针遍历
     * 两个链表长度相减，较长的链表挪动到差值处的下标，两边同等位置遍历,
     * 相等时即为相交初始位置，null为不相交
     * 时间复杂度 O(m+n)
     * 空间复杂度 O(1)
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        int L1 = 0, L2 = 0, diff = 0;
        ListNode head1 = headA, head2 = headB;
        //统计两个链表长度L1和L2
        if (head1 != null) {
            L1++;
            head1 = head1.next;
        }
        if (head2 != null) {
            L1++;
            head2 = head2.next;
        }
        //两个链表的差值
        if (L1 < L2) {
            head1 = headB;
            head2 = headA;
            diff = L2 - L1;
        } else {
            head1 = headA;
            head2 = headB;
            diff = L1 - L2;
        }
        for (int i = 0; i < diff; i++) {
            //较长链表的指针先挪动
            head1 = head1.next;
        }
        while (head1 != null && head2 != null) {
            if (head1 == head2) {
                return head1;
            }
            head1 = head1.next;
            head2 = head2.next;
        }
        return null;
    }
}
